def question1(a, b, c, d):
    def f(a, b, c, d, x):
        return a * x ** 3 + b * x ** 2 + c * x + d
    
    def precision(num):
        str_num = str(num)
        if len(str_num.split('.')[1]) >= 4:
            return True
        return False

    def f_derivative(a, b, c, d, i, j):
        new_num = (i+j)/2
        if precision(new_num):# 判断精度
            return new_num

        if new_num > 0:
            if f(a, b, c, d, i) < 0:
                return f_derivative(a, b, c, d, i, new_num)
            else:
                return f_derivative(a, b, c, d, j, new_num)

    ans = []
    for i in range(0, 4, 0.5):
        if f(a, b, c, d, i) * f(a, b, c, d, i/2) < 0:
            ans.append(f_derivative(a, b, c, d, i, i/2))

    for i in range(3, 8, 0.5):
        if f(a, b, c, d, i) * f(a, b, c, d, i/2) < 0:
            ans.append(f_derivative(a, b, c, d, i, i/2))
            
    for i in range(7, 11, 0.5):
        if f(a, b, c, d, i) * f(a, b, c, d, i/2) < 0:
            ans.append(f_derivative(a, b, c, d, i, i/2))

    return ans
        

def question2(standard, data:list):
    from bisect import bisect_left
    sorted_data = sorted(data)
    mark = bisect_left(sorted_data, standard)
    ans = sorted_data[mark:]
    return ans

    

def question3(h, miles: list):
    def pace(h, miles, max_miles, lenge_miles):
        time = 0
        sorted_miles = sorted(miles, reverse = True)
        for v in range(max_miles - 1, 0, -1):
            for i in range(lenge_miles):
                remainder_mile = sorted_miles[i] - v
                while remainder_mile >= 0:
                    if remainder_mile - v < 0 and remainder_mile > 0:# 休息时间
                        time += 1
                    remainder_mile -= v
                    time += 1
                    if time == h:# 临界条件
                        return v
            
    max_miles = max(miles)
    lenge_miles = len(miles)
    if lenge_miles == h:
        return max_miles
    elif lenge_miles < h:
        return 0
    elif lenge_miles > h:
        return pace(h, miles, max_miles, lenge_miles)



def question4(m, n):
    outer_n = n
    def sum(m):
        if m == outer_n:
            return m
        return m + sum(m+1)
    
    return sum(m)



def question5():
    def sum(num, count):
        if count == 10:
            return num
        count += 1        
        return sum((num+1)*2, count)

    return sum(1, 0)



def question6(root):
    class TreeNode:
        def __init__(self, val = 0, left = None, right = None):
            self.val =val
            self.left = left
            self.right = right

    
    def record(root):
        if not root:
            return

        ans = []
        queue = [root]
        while queue:
            node = queue.pop(0)
            ans.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right) 

        return ans

    return record(root)



def question7(mp): # 暴力。。。
    _mp = mp
    row = len(_mp)
    column = len(_mp[0])
    for r in range(1, row-1):  # 中间情况
        for c in range(column):
            if _mp[r][c] == 1 and (_mp[r][c-1] == 0 or _mp[r][c+1] == 0 or _mp[r-1][c] == 0 or _mp[r+1][c] == 0):
                _mp[r][c] = 9

    for c in range(column): # 第一行情况
        if _mp[0][c] == 1 and (_mp[0][c-1] == 0 or _mp[0][c+1] == 0 or _mp[1][c] == 0):
            _mp[0][c] = 9
    
    return _mp



def question8(mp):
    row = len(mp)
    column = len(mp[0])

    def mark_dfs(mp, r, c):
        if r < 0 or r >= row or c < 0 or c >= column:
            return 

        if mp[r][c] == 0:
            return
        
        mp[r][c] = 0 # 标记
        mark_dfs(mp, r+1, c)
        mark_dfs(mp, r-1, c)
        mark_dfs(mp, r, c+1) 
        mark_dfs(mp, r, c-1)
         
    count = 0    
    for r in range(row):
        for c in range(column):
            if mp[r][c] == 1:
                count += 1
                mark_dfs(mp, r, c)

    return count



def question9(mp):
    row = len(mp)
    column = len(mp[0])
    for r in range(row):
        for c in range(column):
            if mp[r][c] == 0 and (mp[r-1][c] == 1 or mp[r+1][c] == 1 or mp[r][c-1] == 1 or mp[r][c+1] == 1):
                mp[r][c] = -1

    def mark_dfs(mp, r, c):
        if r < 0 or r >= row or c < 0 or c >= column:
            return

        if mp[r][c] == 1:
            return 
        
        mp[r][c] = 1 # 标记
        mark_dfs(mp, r+1, c)
        mark_dfs(mp, r-1, c)
        mark_dfs(mp, r, c+1) 
        mark_dfs(mp, r, c-1)

    count = 0
    for r in range(row):
        for c in range(column):
            if mp[r][c] == 0:
                count += 1
                mark_dfs(mp, r, c)

    return count



def question10(mp):# 数学方法
    from math import factorial
    row = len (mp)
    column = len(mp[0])
    return factorial(row + column -2)



def question11(importance):
    outer_lenge = len(importance)
    memo = {}

    def L(importance, i):
        if i in memo:
            return memo[i]
    
        if i >= outer_lenge:
            return 0
    
        value1 = importance[i] + L(importance, i + 2)# 选
        value2 = L(importance, i + 1) # 不选
    
        memo[i] = max(value1, value2)# 取最大值
        
        return memo[i]

    return L(importance, 0)



def question12(cap, weight:list, value:list):
    def choose(cap, weight, value, i, current_weight):

        new_weight = current_weight + weight[i]# 计算新的重量
    
        if new_weight > cap:# 超出容量，返回负无穷， 强制不可选
            return float('-inf')
    
        return value[i] + max_value(cap, weight, value, i + 1, new_weight)

    def not_choose(cap, weight, value, i, current_weight):
        
        return max_value(cap, weight, value, i + 1, current_weight)

    def max_value(cap, weight, value, i, current_weight):
    
        if i >= len(weight):# 临界条件
            return 0
    
        val_choose = choose(cap, weight, value, i, current_weight)
        val_not_choose = not_choose(cap, weight, value, i, current_weight)
    
        return max(val_choose, val_not_choose)
    
    return max_value(cap, weight, value, 0, 0)




            


